package ljl.alg.jianzhioffer.round2;

/**
 * 没想到怎么搞
 * 其实是先异或得到一个数字
 * 既然是异或，两个数字在这个最低位的二进制位必不相同
 *
 * 故根据这一位，把数组分成两组，然后挨个异或，就得到了结果
 * */
public class _56_1_two_single_numbers {
    
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, m = 1;
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        /*
        * 这个错误犯了好几次了，不能和 1 比价，应该和 0 比较
        * 如果想和 1 比较也可以，你得不停地移位！
        * */
//        for (int i = 0; i < 32; i++) {
//            if ((xor & m) == 1) break;
//            m <<= 1;
//        }
        while ((xor & m) == 0)
            m <<= 1;
        for (int num : nums) {
            if ((num & m) == 0) x ^= num;
            else y ^= num;
        }
        return new int[] {x, y};
    }
}
